Tags: lecture-05, recursion, binary search
Suppose binary_search is called on a sorted array of size \(n\). In total, how many recursive calls to binary_search are made in the worst case?
\(\Theta(\log n)\)
Tags: lecture-05, binary search
Consider the version of binary search shown below:
import math
def binary_search(arr, t, start, stop):
"""
Searches arr[start:stop] for t.
Assumes arr is sorted.
"""
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)True or false: if the target element t occurs multiple times in the array, binary_search is guaranteed to return the first occurrence.
You may assume that arr is sorted and that binary_search(arr, t, 0, len(arr)) is called.
False.
Binary search returns as soon as arr[middle] == t, which may be any of the copies. For example, with arr = [5, 5, 5] and t = 5, the first middle index is 1, so it returns 1 rather than 0.
Tags: lecture-05, binary search
Consider the code below, which shows binary_search as discussed in lecture, but with one additional line: a print statement.
import math
def binary_search(arr, t, start, stop):
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
print(arr[middle]) # <---- this line is new
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)Suppose this version of binary search is called on an array and with a target of t = 7. Which of the following statements is true?
Some of the printed values may be less than or equal to 7, and some may be greater than or equal to 7.
Tags: lecture-05, binary search
Consider the version of binary search shown below. This is the same as the code given in lecture, except that a single print statement has been added. This print statement prints the value of stop at the beginning of each call to binary_search.
import math
def binary_search(arr, t, start, stop):
"""
Searches arr[start:stop] for t.
Assumes arr is sorted.
"""
print(stop) # <-- added print statement
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)Suppose binary_search is called on a sorted list with start = 0 and stop = len(n). True or False: the numbers printed must be a non-increasing sequence. That is, if \(x\) is printed before \(y\), then it must be the case that \(x \geq y\).
True.
Each recursive call either keeps the same stop(searching the right half) or sets stop = middle(searching the left half). Since middle < stop, stop never increases from one call to the next.
Tags: lecture-05, binary search
Consider the following array:
[1, 4, 7, 8, 8, 10, 15, 51, 60, 65, 71, 72, 101]Assume a binary search is being used to determine if the number 2 is in the array, using the implementation of binary_search below (from lecture) and starting with the call binary_search(arr, 2, 0, len(arr)).
import math
def binary_search(arr, t, start, stop):
"""
Searches arr[start:stop] for t.
Assumes arr is sorted.
"""
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)How many total calls to binary search are made (including the first call)?
Answer: 5. On the first call, we guess that index 6 contains the target. The value at index 6 is 15, which is too high, so we make a recursive call with start = 0 and stop = 6.
On the second call, we guess that the item at index 3 is the target. The value at index 3 is 8. This is too large, so we make a recursive call with start = 0 and stop = 3.
On the third call, we guess that the item at index 1 is the target. The value at index 1 is 4. This is too large, so we make a recurse call with start = 0 and stop = 1.
On the fourth call, we are searching a subarray of size 1. We guess that the item at index 0 is equal to the target. This item has value 1, which is too low, therefore we make a recursive call with start = 1 and stop = 1.
On the fifth call overall, we are searching an empty subarray, since start == stop == 1. The implementation of binary search above checks for this case, and returns None; we have reached the base case. Therefore, recursion stops, and we make 5 calls in total.
Tags: lecture-05, binary search
Suppose a binary search is performed on the following array using the implementation of binary_search below (from lecture), starting with the call binary_search(arr, target, 0, len(arr)).
import math
def binary_search(arr, t, start, stop):
"""
Searches arr[start:stop] for t.
Assumes arr is sorted.
"""
if stop - start <= 0:
return None
middle = math.floor((start + stop)/2)
if arr[middle] == t:
return middle
elif arr[middle] > t:
return binary_search(arr, t, start, middle)
else:
return binary_search(arr, t, middle+1, stop)The array is:
[1, 4, 7, 8, 8, 10, 15, 51, 60, 65, 71, 72, 101]What is the greatest number of calls to binary search that can be made to find a target in this array, assuming the target is in the array?
Answer: 4. There are 13 numbers in the array. On the first call, we guess that the target is at index \(\lfloor 13 / 2 \rfloor = 6\). This splits the array exactly in half, so no side is larger than the other and either possible recursive call is just as bad. Let's say we recurse on arr[0:6]. On this second call, we guess that the target is at index 3.
In the worst case, this guess was wrong, so we make another recursive call, either on arr[0:3], or arr[4:6]. The first of these possibilities is worse, since it is larger. On the third recursive call, then, we look through arr[0:3], guessing that the target is at index 1.
In the worst case, it is not, so we make one more additional recursive call (for a total of 4), either on arr[0] or arr[2]. Since we were told to assume that the element is in the array, this recursive call will find that arr[middle] == target and will return middle.
Tags: lecture-05, loop invariants, binary search
Consider iterative_binary_search below and note the print statement in the while-loop:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return NoneSuppose iterative_binary_search is run on the array:
[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]with target 11.
What will be the last value of arr[start] printed?
10
Tags: lecture-05, recursion, binary search
Suppose binary_search has been called on a sorted array arr with a target t that is not necessarily in the array, and with start and stop indices start and stop, respectively (remember, our convention is that the start index is included, while the stop index is excluded from the search). Which of the following must be true? Mark all which apply. You may assume that stop - start\(\geq 1\).
Note: remember that any statement about an empty array is considered to be automatically true. Also, you cannot assume that this call to binary_search is the root call (it could be a recursive call).
The last two answers are both correct.
Tags: lecture-05, verifying recursion, binary search
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)Which of the following statements about the correctness of new_binary_search is true? You may assume that arr will be a list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop
= len(arr) - 1.
new_binary_search may recurse infinitely
Tags: lecture-05, recursion, binary search, verifying recursion
Suppose we modify binary_search so that instead of using the floor operation to find the middle element of the array, we use the ceiling operation (recall that the ceiling of a real number \(x\) is the smallest integer that is \(\geq x\)). The full code is shown below for convenience:
import math
def new_binary_search(arr, start, stop, target):
if stop <= start:
return None
middle = math.ceil((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] < target:
return new_binary_search(arr, middle + 1, stop, target)
else:
return new_binary_search(arr, start, middle, target)You may assume that arr will be a sorted list containing at least one number, and that the initial call to new_binary_search will be with start = 0 and stop = len(arr).
True or False: there are input arrays on which new_binary_search will recurse infinitely.
True.
Consider arr = [1, 2] with target = 0. The first call computes middle = 1, and since \(2 > 0\) it recurses with start = 0, stop = 1. There, middle is \(\lceil 1/2 \rceil = 1\) again, and since \(2 > 0\) it makes the same call, start = 0, stop = 1, forever. The problem is that when stop = start + 1, the ceiling gives middle = stop, so the left recursion doesn't shrink the range.
True or False: there are input arrays on which new_binary_search will raise an IndexError because it attempts to access an element of the array which does not exist.
True.
If arr has one element, the first call has start = 0 and stop = 1, so middle is \(\lceil 1/2 \rceil = 1\), and arr[1] doesn't exist. In general, whenever stop = start + 1, the ceiling makes middle = stop, which is outside the range being searched.
Tags: lecture-05, best and worst case, binary search
What is the worst case time complexity of binary search on an array of size \(n\) under the assumption that the target is guaranteed to appear in the array more than \(n/6\) times? You may assume that the input array is sorted.
\(\Theta(1)\). When there are at least n/6 instances of the target, binary search will not recurse more than twice. On the first recursive call, the array is halved in size. On the second, the array is down to \(n/4\). Note that all of the \(n/6\) instances of the target must be in this chunk of size \(n/4\), and so the middle number must be an instance of the target, and binary search will terminate.
Since binary search cannot recurse more than twice, and since it does constant work on each recursion, the total time taken is bounded by a constant, no matter how large the input array is.
If this seems odd, think about a simpler case: when the target appears \(n/2\) times. In other words, a full half of the array is the target. In this case, we'll make only one call (or maybe two, depending on the value of the middle element). And so there, too, the number of calls is bounded by a constant, and the total time is \(\Theta(1)\).
Tags: lecture-05, binary search
Consider the problem of searching for an element t in a sorted array, with the added requirement that if t is in the array multiple times, we return the index of the first occurrence. For example, if arr = [3, 4, 4, 4, 5, 8], and t = 4, the code should return 1, since the first 4 is at index one.
binary_search as implemented in lecture may not necessarily return the index of the first occurrence of t, but it can be modified so that it does.
Fill in the blanks below so that the function returns the index of the first occurence of t. Hint: last_seen should keep track of the index of the last known occurrence of t.
import math
def mbs(arr, t, start, stop, last_seen=None):
if stop - start <= 0:
return last_seen
middle = math.floor((start + stop) / 2)
if arr[middle] == t:
# _________ <-- fill this in
elif arr[middle] < t:
# _________ <-- fill this in
else:
# _________ <-- fill this inHere is how the blanks should be filled in:
if arr[middle] == t:
return mbs(arr, t, start, middle, middle)
elif arr[middle] < t:
return mbs(arr, t, middle + 1, stop, last_seen)
else:
return mbs(arr, t, start, middle, last_seen)If we see arr[middle] == t, we know that this is either the first occurrence of t in the array, or the first occurrence of t in the left half of the array. Therefore, we make a recursive call to mbs on the left half of the array, keeping track of middle as the index of the leftmost occurrence of t we have seen so far (this is done by passing it as the value to last_seen).
The other recursive calls are the same as in the original binary_search function, except that we pass last_seen as an argument to the recursive calls. This is because we want to keep track of the leftmost occurrence of t we have seen so far.
Eventually, we will reach a point where stop - start <= 0. At this point, we return last_seen, which is the index of the leftmost occurrence of t we have seen so far. This will necessarily be the leftmost occurrence of t in the array.
Tags: loop invariants, lecture-06, binary search
Consider the iterative implementation of binary search shown below:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return NoneWhich of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.
The first option is correct.